/*
 * @Author: w
 * @Date: 2022-02-21 22:56:07
 * @Description: 剑指 Offer 53 - II. 0～n-1中缺失的数字
 */

// 递增排序  二分查找

/**
 * @param {number[]} nums
 * @return {number}
 */

// 循环
var missingNumber = function (nums) {
  for (let i = 0; i < nums.length + 1; i++) {
    if (nums[i] != i) {
      return i;
    }
  }
};

// 数学公式
var missingNumber = function (nums) {
  let n = nums.length;
  // 公式：(首项 + 末项) * 项数 / 2
  let expect = ((0 + n) * (n + 1)) / 2;
  // 数组求和
  let sum = nums.reduce((prev, next) => prev + next, 0);
  return expect - sum;
};

// 二分查找;
// 左侧坐标left正好是答案
var missingNumber = function (nums) {
  let left = 0,
    right = nums.length - 1;
  // 左闭右闭区间
  while (left <= right) {
    let mid = left + ((right - left) >> 1);
    /* 把整个数组看成
    左子数组： nums[i] = i
    右子数组： nums[i] != i */
    // 当中间元素跟索引相等，那就应该去右子数组中查找
    if (nums[mid] == mid) left = mid + 1;
    // 如果不等的话，就去找左子数组中查找，因为我们本质上是要找不相等的第1个（或者说最左边的那个）
    else right = mid - 1;
  }
  return left;
};
